package Modelo;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Vector;

public class BusquedaAsterisco {

	Vector costoTotalL = new Vector();
	int acumulador = 0;

	public ArrayList<Integer> busquedaAsterisco(int[] vector) {
		ArrayList flips = new ArrayList();

		ArrayList cerrado = new ArrayList();
		ArrayList abierto = new ArrayList();
		ArrayList<Arbol> ordenHeuristico = new ArrayList<Arbol>();

		Arbol padre = new Arbol();
		padre.setVector(vector);
		abierto.add(padre);

		while (!estadoFinal(((Arbol) abierto.get(0)).getVector())) {
			
			if (exiteCerrado(cerrado, ((Arbol) abierto.get(0)).getVector())) {
				abierto.remove(0);
			} else {
				Arbol record = (Arbol) abierto.get(0);
				int[] temp = ((Arbol) abierto.get(0)).getVector();
				abierto.remove(0);

				int[] vec = new int[temp.length];
				for (int p = 0; p < temp.length; p++) {
					vec[p] = temp[p];
				}
				cerrado.add(vec);
				int[] rec;
				for (int pos = 1; pos < temp.length; pos++) {
					rec = new int[temp.length];
					for (int p = 0; p < temp.length; p++) {
						rec[p] = temp[p];
					}
					int[] vfl = new int[pos + 1];
					int j = 0;
					for (int i = pos; i >= 0; j++) {
						vfl[j] = rec[i];

						i--;
					}

					for (int i = pos; i >= 0; i--) {
						rec[i] = vfl[i];
					}

					vec = new int[temp.length];
					for (int p = 0; p < temp.length; p++) {
						vec[p] = rec[p];
					}
					Arbol ap = new Arbol();
					ap.setVector(vec);
					for (Iterator localIterator = record.getAnterior()
							.iterator(); localIterator.hasNext();) {
						int m = ((Integer) localIterator.next()).intValue();
						ap.getAnterior().add(Integer.valueOf(m));
					}
					ap.getAnterior().add(Integer.valueOf(pos + 1));
					int heu = calcularHeuristica(vec);
					int pesoNodo = 1;
					int pesoTotal = pesoNodo + heu;

					ap.setHeuristica(heu);
					ordenHeuristico.add(ap);

					costoTotalL.add(pesoTotal);

				}

				Collections.sort(ordenHeuristico, new CompareToHeur());

				for (Arbol ap : ordenHeuristico) {
					abierto.add(0, ap);

					if (costoTotalL.size() >= 3) {

						int nMayor = Integer.parseInt(costoTotalL.get(0)
								.toString());
						int posMayor = 0;

						for (int i = 0; i < costoTotalL.size(); i++) {
							if (Integer.parseInt(costoTotalL.get(i).toString()) > nMayor) {
								nMayor = Integer.parseInt(costoTotalL.get(i)
										.toString());
								posMayor = i;
							}
						}

						costoTotalL.remove(posMayor);
					}
				}
				if (costoTotalL.size() >= 1) {
					retornarCostoTot();
				}

				ordenHeuristico = new ArrayList();
			}
		}

		flips = ((Arbol) abierto.get(0)).getAnterior();
		return flips;
	}

	public void imprime(ArrayList lista) {

		for (int i = 0; i < lista.size(); i++) {
			System.out.println(lista.get(i));
		}
	}

	public int retornarCostoTot() {

		int nMenor = Integer.parseInt(costoTotalL.get(0).toString());

		for (int i = 0; i < costoTotalL.size(); i++) {
			if (Integer.parseInt(costoTotalL.get(i).toString()) < nMenor) {
				nMenor = Integer.parseInt(costoTotalL.get(i).toString());
			}
		}
		acumulador = acumulador + nMenor;

		return acumulador;
	}

	public int calcularHeuristica(int[] vector) {
		int[] vect = new int[vector.length];
		for (int p = 0; p < vector.length; p++) {
			vect[p] = vector[p];
		}
		ArrayList fl = new ArrayList();

		for (int posCola = vect.length - 1; posCola > 0; posCola--) {
			int posCabeza = posCola;
			int valorCola = vect[posCola];
			for (int i = posCola - 1; i >= 0; i--) {
				if (vect[i] > valorCola) {
					valorCola = vect[i];
					posCabeza = i;
				}
			}

			if (posCabeza == posCola)
				continue;
			if (posCabeza != 0) {
				int[] tempo = new int[posCabeza + 1];
				int o = 0;

				for (int i = posCabeza; i >= 0; o++) {
					tempo[o] = vect[i];

					i--;
				}

				for (int i = posCabeza; i >= 0; i--) {
					vect[i] = tempo[i];
				}
				fl.add(Integer.valueOf(posCabeza + 1));
			}

			int[] tempo = new int[posCola + 1];
			int o = 0;

			for (int i = posCola; i >= 0; o++) {
				tempo[o] = vect[i];

				i--;
			}

			for (int i = posCola; i >= 0; i--) {
				vect[i] = tempo[i];
			}

			fl.add(Integer.valueOf(posCola + 1));
		}

		int heu = fl.size();
		return heu;
	}

	public boolean exiteCerrado(ArrayList<int[]> lista, int[] ent) {
		boolean resp = false;
		for (int[] vec : lista) {
			int iguales = 0;
			for (int i = 0; i < ent.length; i++) {
				if (ent[i] == vec[i]) {
					iguales++;
				}
			}
			if (iguales == ent.length) {
				resp = true;
			}
		}
		return resp;
	}

	public boolean estadoFinal(int[] ent) {
		boolean resp = true;
		for (int i = 0; i < ent.length; i++) {
			if (ent[i] != i + 1) {
				resp = false;
			}
		}
		return resp;
	}

	public class CompareToHeur implements Comparator<Arbol> {

		public int compare(Arbol a, Arbol b) {
			return b.getHeuristica() - a.getHeuristica();
		}
	}
}